#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
typedef long long ll;
const int INF=1e9+7;
    int countPaths(int n, vector<vector<int>>& roads) {
        int m=roads.size();
        vector<vector<tuple< int ,ll>>> g(n);
        for(int i=0;i<m;++i)
        {
            auto& e=roads[i];
            g[e[0]].emplace_back(e[1],e[2]);
            g[e[1]].emplace_back(e[0],e[2]);
        }
        vector<ll> d(n,LLONG_MAX);
        priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<>>q ;
        d[0]=0;
        q.emplace(0,0);
        while(!q.empty())
        {
            auto [d_x,x]=q.top();
            q.pop();
            if(d_x>d[x]) continue;
            for(auto&[y,d_y]:g[x])
            {
                ll new_d=d_y+d_x;
                if(new_d<d[y])
                {
                    d[y]=new_d;
                    q.emplace(d[y],y);
                }
            }
        }
        vector<bool> visit(n);
        vector<ll> prev(n,-1);
        function<int(int)> dfs=[&](int x)
        {
            visit[x]=true;
            int ret=0;
            if(x==0) return 1;
            for(auto& [y,d_y]:g[x])
            {
                if(d_y+d[y]==d[x])
                {
                    if(visit[y]&&prev[y]!=-1)
                    ret+=prev[y];
                    else
                    {
                        ret+=dfs(y);
                    }
                    ret%=INF;
                }
            }
            prev[x]=ret;
            return ret;
        };
        return dfs(n-1);

    }
};